Japanese Patent Application No. 10-373384 has not been published in English under Article 21(2) of the Patent Cooperation Treaty.
This application is based on Japanese Patent Application No. 10-373384, filed Dec. 28, 1998, the contents of which is incorporated herein by reference.
The present invention relates to a data search apparatus and an internetwork relay apparatus which mutually connects a plurality of networks such as LAN (Local Area Network), WAN (Wide Area Network), and the like to one another to perform data exchange and relay in a data link layer and a network layer.
In a communication network system including such a network as LAN, WAN, and the like, an internetwork relaying apparatus which is called a router, a layer 3 switch or the like has been used.
In general, an apparatus of this type determines a transmission destination from a destination address of a received frame to perform relay processing for transmitting the frame to a desired destination, in which the relay processing is performed for each processing of frame receipt, protocol analysis, destination determination and frame destination processings.
FIG. 1 illustrates one example of a configuration of a conventional internetwork relay apparatus which comprises a frame receipt portion 11, a frame buffer 12, a protocol analysis portion 13, a destination determination portion 14, a forwarding table 15, a frame transmission portion 16, and a control portion 17.
The frame receipt portion 11 receives a frame transmitted from an upstream network (not shown) to store the received frame in the frame buffer 12. Then, for each completion of reception of the frame, the frame receipt portion 11 notifies the control portion 17 of completion of reception and receives a frame buffer address for storing the next frame from the control portion 17.
When the protocol analysis portion 13 is notified from the control portion 17 that an unprocessed frame has been stored in the frame buffer 12, it reads frame data from the frame buffer 12 to perform a determination about a layer 2 frame form and a layer 3 protocol of the frame using a comparator inside the protocol analysis portion 13. Then, after completion of the determination, the protocol analysis portion 13 stores the determination result in the frame buffer 12 and notifies a completion notification to the control portion 17. Also, when another unprocessed frame has been stored in the frame buffer 12, further protocol analysis processing is performed.
When the destination determination portion 14 is notified from the control portion 17 that an unprocessed frame has been stored in the frame buffer 12, it reads a destination address included in a header of the received frame from the frame buffer 12 to determine a destination of the frame using the forwarding table 15. Then, after completion of the determination, the destination determination portion 14 stores the destination of the frame in the frame buffer 12 and notifies a completion notification to the control portion 17. This destination determination processing is performed on each of all the unprocessed frames which have been stored in the frame buffer 12.
Since processings to be performed and data positions to be processed are different due to difference in layer 2 frame form and layer 3 protocol, the destination determination processing is performed by reading the frame data, after the determination results about the layer 2 frame form and the layer 3 protocol which have been obtained by the protocol analysis portion 13 and which have been stored in the frame buffer 12 is read out.
As soon as the frame transmission portion 16 is notified from the control portion 17 that a frame to be transmitted has been stored in the frame buffer 12, it reads a destination to be transmitted and a data frame to be transmitted on the basis of the frame buffer address which has been notified from the control portion 17 to transmit the same to a desired destination. Then, when the transmission is completed, a completion notification is notified to the control portion 17.
The control portion 17 performs control among respective processings and manages a frame buffer address in which an unprocessed frame has been stored for each processing.
The protocol analysis portion 13 is configured in the following manner. FIG. 2 is a circuit block diagram showing a configuration of the protocol analysis portion 13. That is, the protocol analysis portion 13 comprises a protocol analysis processing control portion 21, and a plurality of comparators 221 to 22n provided so as to correspond to types of the layer 2 frame form and the layer 3 protocol.
As soon as the protocol analysis processing control portion 21 is notified from the control portion 17 that an unprocessed frame has been stored in the frame buffer 12, it reads the frame data from the frame buffer 12 on the basis of the frame buffer address which has been notified from the control portion 17, and notifies the respective comparators 221 to 22n of what byte the read data is from a head of the frame.
Data (field data representing a protocol) to be compared with the frame data read from the frame buffer 12 is preliminarily stored in each of the comparators 221 to 22n, and the respective comparators 221 to 22n determine which of set data the read data coincides with. When the read data coincides with any of the set data, the layer 2 frame form and the layer 3 protocol of the frame are identified. Also, a data position to be compared is preliminarily set with the number of bytes counted from a head of a frame for each of the comparators 221 to 22n, and data to be compared is inputted to each of the comparators 221 to 22n, taking account of the position information provided from the protocol analysis processing control portion 21.
For example, in a comparator where a frame format having a DIX (DEC/Intel/Xerox) as the layer 2 frame form and an IPv4 as the layer 3 protocol on Ethernet is identified, the following identification processing is performed. That is, in order to identify the frame format having the DIX and the IPv4, it is required that Type field positioned at the 13th to the 14th bytes is 0x0800. Therefore, in the comparator, data to be compared is set to 0x0800 and the position is set to the 13th to the 14th bytes.
Also, in order to identify a frame format where the layer 2 frame form is LLC (Logical Link Control) header+SNAP (Subnetwork Packet Protocol) on Ethernet and the layer 3 protocol is IPX (Internetwork Packet Exchange), it is required that the 13th to the 14th bytes of a frame are at most 1500 and the 15th to the 22th bytes are 0xAAAA030000008137. For this reason, in the comparator for identifying this frame format, a circuit for determining that the 13th and the 14th bytes are less than or equal to 1500 and information for indicating that the 15th to the 22th bytes is 0xAAAA030000008137 are set.
When the protocol analysis processing control portion 13 is notified of correspondence of data from any one of the comparators, the corresponding layer 2 frame form and the layer 3 protocol are respectively written in the same frame buffer region where the frame data has been stored. Then, after the writing, the control portion 17 is notified of completion of the protocol analysis.
However, there are the following problems to be solved in a conventional apparatus for performing such protocol processings. That is, the reason why the protocol analysis is required is because it is assumed that a plurality of layer 3 protocols which have been received in a plurality of layer 2 frame forms are processed in a relay processing. In a conventional approach, since the comparators 221 to 22n for identification are provided for respective layer 2 frame forms and layer 3 protocols, a circuit for the protocol analysis portion 13 is large-scaled when the number of kinds of layer 2 frame forms and layer 3 protocols is increased.
Also, when a novel layer 2 frame form or a novel layer 3 protocol must be identified, a dedicated comparator must be added. Therefore, a hardware change may be required for each of a novel issue, a modification and the like of standard/reference or for each specification change.
On the other hand, it is thought that a conventional memory is used for identification of a layer 2 frame form and a layer 3 protocol. In this case, entries used to make a determination for each layer 2 frame form and layer 3 protocol are read one by one, the entries are sequentially compared with the frame to be processed, and a series of processings are performed repeatedly until an entry coinciding with the frame to be processed is found out. Accordingly, when the number of readings of entry is increased, processing performance is lowered.
An object of the present invention is to provide an internetwork relay apparatus which makes a number of comparators unnecessary to reduce a circuit scale and easily accommodates to change in standard and/or specification, and which makes a number of memory read operations unnecessary to maintain processing performance high.
In order to achieve the above object, the present invention is an internetwork relay apparatus where, from the contents of field data of a received transmission frame, a form and a protocol of the transmission frame are analyzed and a relay processing is performed on the transmission frame according to the analyzed result, comprising a content addressable memory where field data representing a frame form and a protocol of each of all transmission frames to be subjected to relay processing is divided into a plurality of portion data each having a predetermined length, a plurality of search sequences different from one another are set on the basis of the portion data, and, for each of the search sequences, associative data representing the contents of search control in the sequence is preliminarily stored so as to be associated with the portion data configuring the search sequence and a search identifier representing the search sequence. Then, each time when the received transmission frame is stored in a frame buffer memory, one of the portion data of the transmission frame is selectively read out from the field data of the transmission frame and a search in the content addressable memory is performed on the basis of the read portion data and the search identifier representing the search sequence by first search means. Also, another portion data of the field data is read from the frame buffer memory according to an instruction of the associative data read from the content addressable memory, and a search in the content addressasble memory is performed on the basis of the read other portion data and the search identifier included in the associative data by second search means. The internetwork relay apparatus is also provided with determination means where a search completion or a search continuation is determined on the basis of the contents of the associative data read from the content addressable memory by the first and second search means. In a case of the search continuation, search processing by the second search means is performed repeatedly, while information representing the form and protocol of the received transmission frame included in the above read associative data is output in a case of the search termination.
Thus, according to the present invention, for example, analysis of a layer 2 frame form and a layer 3 protocol can be identified by data which has been registered in the content addressable memory. Accordingly, even when there are many types of layer 2 frame forms and layer 3 protocols to be identified, it is unnecessary to provide comparators for the respective types so that a circuit scale of a protocol analysis portion can be maintained constant.
Also, even when it is necessary to identify a novel layer 2 frame form or a novel layer 3 protocol, such an identification can be performed only by registering corresponding data in the content addressable memory, and it is unnecessary to add a new circuit.
Furthermore, since a search is performed in the content addressable memory with a combination of a portion of field data and a search identifier as a key, even when data in different regions in a frame to be searched are the same, the data are prevented from being processed or handled as the same entry because values of search identifiers are different from each other. Namely, a difference between layer 2 frames or a difference between layer 3 protocols can be correctly determined.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.